{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approaches to modeling and simulation\n",
    "\n",
    "`DiscreteEvents.jl` supports different approaches to modeling and simulation of *discrete event systems (DES)*. It provides three major schemes: 1) an event-scheduling scheme, 2) a process-oriented scheme and 3) continuous sampling. With them different modeling strategies can be applied.\n",
    "\n",
    "A problem can be expressed differently through various modeling approaches. A simple problem can illustrate this :\n",
    "\n",
    "> A server *takes* something from an input, *processes* it for some time and\n",
    "> *puts* it out to an output. There are 8 servers in the system, 4 foos and 4 bars\n",
    "> interacting with each other via two channels.\n",
    "\n",
    "\n",
    "## Event based modeling\n",
    "\n",
    "In this view *events* occur in time and trigger further events. Here the three server actions are seen as events and can be described in an event graph:\n",
    "\n",
    "![event graph](../src/images/event.png)\n",
    "\n",
    "You define a data structure for the server, provide functions for the three actions, create channels and servers and start:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.01: foo 4 took token 1\n",
      " 0.12: bar 6 took token 5\n",
      " 0.29: foo 1 took token 30\n",
      " 0.77: bar 8 took token 31\n",
      " 1.64: foo 2 took token 248\n",
      " 2.26: bar 3 took token 250\n",
      " 2.55: foo 7 took token 750\n",
      " 3.02: bar 5 took token 757\n",
      " 3.30: foo 4 took token 3785\n",
      " 3.75: bar 6 took token 3789\n",
      " 4.34: foo 1 took token 22734\n",
      " 4.60: bar 8 took token 22735\n",
      " 5.31: foo 2 took token 181880\n",
      " 5.61: bar 3 took token 181882\n",
      " 5.90: foo 7 took token 545646\n",
      " 6.70: bar 5 took token 545653\n",
      " 6.91: foo 4 took token 2728265\n",
      " 7.83: bar 6 took token 2728269\n",
      " 8.45: foo 1 took token 16369614\n",
      " 9.26: bar 8 took token 16369615\n",
      " 9.82: foo 2 took token 130956920\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\"run! finished with 20 clock events, 1000 sample steps, simulation time: 10.0\""
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using DiscreteEvents, Printf, Random\n",
    "\n",
    "mutable struct Server1\n",
    "  id::Int64\n",
    "  name::AbstractString\n",
    "  input::Channel\n",
    "  output::Channel\n",
    "  op     # operation to take\n",
    "  token  # current token\n",
    "\n",
    "  Server1(id, name, input, output, op) = new(id, name, input, output, op, nothing)\n",
    "end\n",
    "\n",
    "function take(S::Server1)\n",
    "    if isready(S.input)\n",
    "        S.token = take!(S.input)\n",
    "        @printf(\"%5.2f: %s %d took token %d\\n\", tau(), S.name, S.id, S.token)\n",
    "        event!(SF(put, S), after, rand())         # call put after some time\n",
    "    else\n",
    "        event!(SF(take, S), SF(isready, S.input)) # call again if input is ready\n",
    "    end\n",
    "end\n",
    "\n",
    "function put(S::Server1)\n",
    "    put!(S.output, S.op(S.id, S.token))\n",
    "    S.token = nothing\n",
    "    take(S)\n",
    "end\n",
    "\n",
    "reset!(𝐶)\n",
    "Random.seed!(123)\n",
    "\n",
    "ch1 = Channel(32)  # create two channels\n",
    "ch2 = Channel(32)\n",
    "\n",
    "s = shuffle(1:8)\n",
    "for i in 1:2:8\n",
    "    take(Server1(s[i], \"foo\", ch1, ch2, +))\n",
    "    take(Server1(s[i+1], \"bar\", ch2, ch1, *))\n",
    "end\n",
    "\n",
    "put!(ch1, 1) # put first token into channel 1\n",
    "run!(𝐶, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## State based modeling\n",
    "\n",
    "Here the server has three states: *Idle*, *Busy* and *End* (where *End* does nothing). On an arrival event it resets its internal clock $x=0$ and determines the service time $t_s$, moves to *Busy*, *works* on its input and puts it out when $t_s$ is over. Then it goes back to *Idle*. A state transition diagram (Mealy model) of the timed automaton would look like:\n",
    "\n",
    "![timed automaton](../src/images/state.png)\n",
    "\n",
    "Again you need a data structure for the server (state …). You define states and events and implement a $δ$ transition function with two methods. Thereby you dispatch on states and events. Since you don't need to implement all combinations of states and events, you may implement a fallback transition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.01: foo 4 took token 1\n",
      " 0.12: bar 6 took token 5\n",
      " 0.29: foo 1 took token 30\n",
      " 0.77: bar 8 took token 31\n",
      " 1.64: foo 2 took token 248\n",
      " 2.26: bar 3 took token 250\n",
      " 2.55: foo 7 took token 750\n",
      " 3.02: bar 5 took token 757\n",
      " 3.30: foo 4 took token 3785\n",
      " 3.75: bar 6 took token 3789\n",
      " 4.34: foo 1 took token 22734\n",
      " 4.60: bar 8 took token 22735\n",
      " 5.31: foo 2 took token 181880\n",
      " 5.61: bar 3 took token 181882\n",
      " 5.90: foo 7 took token 545646\n",
      " 6.70: bar 5 took token 545653\n",
      " 6.91: foo 4 took token 2728265\n",
      " 7.83: bar 6 took token 2728269\n",
      " 8.45: foo 1 took token 16369614\n",
      " 9.26: bar 8 took token 16369615\n",
      " 9.82: foo 2 took token 130956920\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\"run! finished with 20 clock events, 1000 sample steps, simulation time: 10.0\""
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "abstract type Q end  # states\n",
    "struct Idle <: Q end\n",
    "struct Busy <: Q end\n",
    "abstract type Σ end  # events\n",
    "struct Arrive <: Σ end\n",
    "struct Leave <: Σ end\n",
    "\n",
    "mutable struct Server2\n",
    "    id::Int64\n",
    "    name::AbstractString\n",
    "    input::Channel\n",
    "    output::Channel\n",
    "    op     # operation to take\n",
    "    state::Q\n",
    "    token  # current token\n",
    "\n",
    "    Server2(id, name, input, output, op) = new(id, name, input, output, op, Idle(), nothing)\n",
    "end\n",
    "\n",
    "arrive(A) = event!(SF(δ, A, A.state, Arrive()), SF(isready, A.input))\n",
    "\n",
    "function δ(A::Server2, ::Idle, ::Arrive)\n",
    "    A.token = take!(A.input)\n",
    "    @printf(\"%5.2f: %s %d took token %d\\n\", tau(), A.name, A.id, A.token)\n",
    "    A.state=Busy()\n",
    "    event!(SF(δ, A, A.state, Leave()), after, rand())\n",
    "end\n",
    "\n",
    "function δ(A::Server2, ::Busy, ::Leave)\n",
    "    put!(A.output, A.op(A.id,A.token))\n",
    "    A.state=Idle()\n",
    "    arrive(A)\n",
    "end\n",
    "\n",
    "δ(A::Server1, q::Q, σ::Σ) =               # fallback transition\n",
    "        println(stderr, \"$(A.name) $(A.id) undefined transition $q, $σ\")\n",
    "\n",
    "reset!(𝐶)\n",
    "Random.seed!(123)\n",
    "\n",
    "ch1 = Channel(32)  # create two channels\n",
    "ch2 = Channel(32)\n",
    "\n",
    "s = shuffle(1:8)\n",
    "for i in 1:2:8\n",
    "    arrive(Server2(s[i], \"foo\", ch1, ch2, +))\n",
    "    arrive(Server2(s[i+1], \"bar\", ch2, ch1, *))\n",
    "end\n",
    "\n",
    "put!(ch1, 1) # put first token into channel 1\n",
    "run!(𝐶, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activity based modeling\n",
    "\n",
    "The server's *activity* is the processing of the token. A timed Petri net would look like:\n",
    "\n",
    "![timed petri net](../src/images/activity.png)\n",
    "\n",
    "The *arrive* \"transition\" puts a \"token\" in the *Queue*. If both \"places\" *Idle* and *Queue* have tokens, the server *takes* them, shifts one to *Busy* and *puts* out two after a timed transition with delay $v_{put}$. Then it is *Idle* again and the cycle restarts.\n",
    "\n",
    "The server's activity is described by the blue box. Following the Petri net, you should implement a state variable with states Idle and Busy, but you don't need to if you separate the activities in time. You need a data structure for the server and define a function for the activity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.01: foo 4 took token 1\n",
      " 0.12: bar 6 took token 5\n",
      " 0.29: foo 1 took token 30\n",
      " 0.77: bar 8 took token 31\n",
      " 1.64: foo 2 took token 248\n",
      " 2.26: bar 3 took token 250\n",
      " 2.55: foo 7 took token 750\n",
      " 3.02: bar 5 took token 757\n",
      " 3.30: foo 4 took token 3785\n",
      " 3.75: bar 6 took token 3789\n",
      " 4.34: foo 1 took token 22734\n",
      " 4.60: bar 8 took token 22735\n",
      " 5.31: foo 2 took token 181880\n",
      " 5.61: bar 3 took token 181882\n",
      " 5.90: foo 7 took token 545646\n",
      " 6.70: bar 5 took token 545653\n",
      " 6.91: foo 4 took token 2728265\n",
      " 7.83: bar 6 took token 2728269\n",
      " 8.45: foo 1 took token 16369614\n",
      " 9.26: bar 8 took token 16369615\n",
      " 9.82: foo 2 took token 130956920\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\"run! finished with 20 clock events, 1000 sample steps, simulation time: 10.0\""
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mutable struct Server3\n",
    "  id::Int64\n",
    "  name::AbstractString\n",
    "  input::Channel\n",
    "  output::Channel\n",
    "  op     # operation\n",
    "  token  # current token\n",
    "\n",
    "  Server3(id, name, input, output, op) = new(id, name, input, output, op, nothing)\n",
    "end\n",
    "\n",
    "arrive(S::Server3) = event!(SF(serve, S), SF(isready, S.input))\n",
    "\n",
    "function serve(S::Server3)\n",
    "    S.token = take!(S.input)\n",
    "    @printf(\"%5.2f: %s %d took token %d\\n\", tau(), S.name, S.id, S.token)\n",
    "    event!((SF(put!, S.output, S.op(S.id, S.token)), SF(arrive, S)), after, rand())\n",
    "end\n",
    "\n",
    "reset!(𝐶)\n",
    "Random.seed!(123)\n",
    "\n",
    "ch1 = Channel(32)  # create two channels\n",
    "ch2 = Channel(32)\n",
    "\n",
    "s = shuffle(1:8)\n",
    "for i in 1:2:8\n",
    "    arrive(Server3(s[i], \"foo\", ch1, ch2, +))\n",
    "    arrive(Server3(s[i+1], \"bar\", ch2, ch1, *))\n",
    "end\n",
    "\n",
    "put!(ch1, 1) # put first token into channel 1\n",
    "run!(𝐶, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Process based modeling\n",
    "\n",
    "Here you combine it all in a simple function of *take!*-*delay!*-*put!* like in the activity based example, but running in the loop of a process. Processes can wait or delay and are suspended and reactivated by Julia's scheduler according to background events. There is no need to handle events explicitly and no need for a server data type since a process keeps its own data. Processes must look careful to their timing and therefore you must enclose the IO-operation in a `now!` call:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.00: foo 1 took token 1\n",
      " 0.79: bar 2 took token 2\n",
      " 1.15: foo 3 took token 4\n",
      " 2.05: bar 4 took token 7\n",
      " 2.58: foo 5 took token 28\n",
      " 2.61: bar 6 took token 33\n",
      " 3.51: foo 7 took token 198\n",
      " 4.45: bar 8 took token 205\n",
      " 5.07: foo 1 took token 1640\n",
      " 5.42: bar 2 took token 1641\n",
      " 5.99: foo 3 took token 3282\n",
      " 6.19: bar 4 took token 3285\n",
      " 6.57: foo 5 took token 13140\n",
      " 7.33: bar 6 took token 13145\n",
      " 7.52: foo 7 took token 78870\n",
      " 7.75: bar 8 took token 78877\n",
      " 7.85: foo 1 took token 631016\n",
      " 8.48: bar 2 took token 631017\n",
      " 9.43: foo 3 took token 1262034\n",
      " 9.97: bar 4 took token 1262037\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\"run! finished with 39 clock events, 0 sample steps, simulation time: 10.0\""
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function simple(input::Channel, output::Channel, name, id, op)\n",
    "    token = take!(input)         # take something, eventually wait for it\n",
    "    now!(SF(println, @sprintf(\"%5.2f: %s %d took token %d\", tau(), name, id, token)))\n",
    "    d = delay!(rand())           # wait for a given time\n",
    "    put!(output, op(token, id))  # put something else out, eventually wait\n",
    "end\n",
    "\n",
    "ch1 = Channel(32)  # create two channels\n",
    "ch2 = Channel(32)\n",
    "\n",
    "for i in 1:2:8    # create and register 8 SimProcesses\n",
    "    process!(SP(i, simple, ch1, ch2, \"foo\", i, +))\n",
    "    process!(SP(i+1, simple, ch2, ch1, \"bar\", i+1, *))\n",
    "end\n",
    "\n",
    "reset!(𝐶)\n",
    "put!(ch1, 1) # put first token into channel 1\n",
    "run!(𝐶, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparison\n",
    "\n",
    "The output of the last example is different from the first three approaches because we did not shuffle (the shuffling of the processes is done by the scheduler). So if the output depends very much on the sequence of events and you need to have reproducible results, explicitly controlling for the events like in the first three examples is preferable. If you are more interested in statistical evaluation - which is often the case -, the 4th approach is appropriate.\n",
    "\n",
    "All four approaches can be expressed in `DiscreteEvents.jl`. Process based modeling seems to be the simplest and the most intuitive approach, while the first three are more complicated. But they are also more structured and controllable , which comes in handy for more complicated examples. After all, parallel processes are often tricky to control and to debug. But you can combine the approaches and take the best from all worlds.\n",
    "\n",
    "## Combined approach\n",
    "\n",
    "Physical systems can be modeled as *continuous systems* (nature does not jump), *discrete systems* (nature jumps here!) or *hybrid systems* (nature jumps sometimes).\n",
    "\n",
    "While continuous systems are the domain of differential equations, discrete and hybrid systems may be modeled easier with `DiscreteEvents.jl` by combining the *event-scheduling*, the *process-based* and the *continuous-sampling* schemes.\n",
    "\n",
    "### A hybrid system\n",
    "\n",
    "(empty)\n",
    "\n",
    "## Theories\n",
    "\n",
    "There are some theories about the different approaches (1) event based, (2) state based, (3) activity based and (4) process based. Choi and Kang [1] have written an entire book about the first three approaches. Basically they can be converted to each other. Cassandras and Lafortune [2] call those \"the event scheduling scheme\" and the 4th approach \"the process-oriented simulation scheme\" [3]. There are communities behind the various views and `DiscreteEvents.jl` wants to be useful for them all.\n",
    "\n",
    "[1]:  [Choi and Kang: *Modeling and Simulation of Discrete-Event Systems*, Wiley, 2013](https://books.google.com/books?id=0QpwAAAAQBAJ)\n",
    "\n",
    "[2]: [Cassandras and Lafortune: *Introduction to Discrete Event Systems*, Springer, 2008, Ch. 10](https://books.google.com/books?id=AxguNHDtO7MC)\n",
    "\n",
    "[3]: to be fair, the 4th approach is called by Choi and Kang \"parallel simulation\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.2.0",
   "language": "julia",
   "name": "julia-1.2"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.2.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
